package com.fulu.javabase.arithmetic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 快速排序算法
 */
public class FastSort {
    public static void main(String[] args) {
//        int [] arr = {85, 76, 2, 99, 31, 29, 46, 22, 58, 99, 3, 74};

        int N=100000;
        int[] arr=new int[N];
        for(int i=0;i<N;i++)
            arr[i]=(int) (Math.random()*9999);

        long start = System.currentTimeMillis();
//        normalSort(arr);  // 8s
            qs(arr, 0, arr.length -1); // 23ms
//        sort(arr, 0, N -1); // 56ms
        long end = System.currentTimeMillis();
        System.out.println(end - start);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 快速排序
     * @param arr
     * @param i
     * @param j
     */
    private static void qs(int[] arr, int i, int j){
        // 首先i必须小于j，此时才需要排序，否则直接结束
        if(i >= j){
            return;
        }
        // 取第一个数作为比较基准
        int base = arr[i];
        // 保存本次循环的开始和结束位置
        int start = i;
        int end = j;
        // i在j的左边则一直循环移动
        while (i < j) {
            // 先看右边元素，当j元素大于等于基准时，证明该元素不需要交换，向左移动一个指针
            while (arr[j] >= base && i < j) {
                j--;
            }
            // 再看左边元素，当i元素小于等于基准时，证明该元素不需要交换，向右移动一个指针
            while (arr[i] <= base && i < j) {
                i++;
            }
            // 找到两个需要交换位置的元素，操作换位
            if(i < j) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        // 循环结束后，基准数的位置固定，将它放到i的位置
        int tmp = arr[i];
        arr[i] = base;
        arr[start] = tmp;
        // 递归排序左右数组,这里必须判断一下，不然对栈造成很大压力，甚至溢出，速度也会很慢
        if(j + 1 < end) {
            qs(arr, j + 1, end);
        }
        if(i - 1 > start) {
            qs(arr, start, i - 1);
        }
    }

    /**
     * 第一版快速排序。。
     * @param arr
     * @return
     */
    private static List<Integer> chai(int[] arr) {
        // 随机找一个基准数，通常取第一个或最后一个
        int base = arr[0];
//        int[] left = new int[arr.length];
//        int[] right = new int[arr.length];
        List<Integer> left = new ArrayList<>();
        List<Integer> right = new ArrayList<>();
        for(int i = 1; i< arr.length; i++){
            if(arr[i] < base){
                left.add(arr[i]);
            }else{
                right.add(arr[i]);
            }
        }
        if(left.size() > 1){
            left =chai(left.stream().mapToInt(Integer::valueOf).toArray());
        }
        if(right.size() > 1){
            right = chai(right.stream().mapToInt(Integer::valueOf).toArray());
        }
        left.add(base);
        left.addAll(right);
        return left;
    }

    /**
     * 网上找的快速排序方法
     * @param array
     * @param begin
     * @param end
     */
    private static void sort(int[] array,int begin,int end){
        int right=end,left=begin;
        while(right!=left){
            for(;right>left;right--){
                if(array[begin]>=array[right])
                    break;
            }
            for(;left<right;left++){
                if(array[begin]<array[left])
                    break;
            }

            if(left!=right){
                int tmp=array[left];
                array[left]=array[right];
                array[right]=tmp;
            }else if(right!=begin){
                int tmp=array[begin];
                array[begin]=array[left];
                array[left]=tmp;
            }
        }

        if(left-1>begin)
            sort(array,begin,left-1);
        if(right+1<end)
            sort(array,right+1,end);
    }

    /**
     * 普通的冒泡排序
     * @param arr
     */
    private static void normalSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if(arr[i] > arr[j]){
                    int tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
    }
}
